# 44/100 二叉树-二叉搜索树中第k小的元素
# leetcode第230题: https://leetcode.cn/problems/kth-smallest-element-in-a-bst/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/13
from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test
from typing import Optional


def kthSmallest_rec(root: Optional[TreeNode], k: int) -> int:
    """使用递归的方法"""

    def in_order(cur: TreeNode):
        nonlocal k, res
        if cur:
            in_order(cur.left)
            k -= 1
            if k == 0:
                res = cur.val
            in_order(cur.right)

    res = 0
    in_order(root)
    return res


def kthSmallest_stack(root: Optional[TreeNode], k: int) -> int:
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k -= 1
        if k == 0:
            return root.val
        root = root.right


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([3, 1, 4, None, 2])
    t2 = TreeConverter.list_to_tree([5, 3, 6, 2, 4, None, None, 1])
    inp = [{"root": t1, "k": 1}, {"root": t2, "k": 3}, ]
    out = [1, 3]
    test.test_function(kthSmallest_rec, inp, out, times=10000)
    test.test_function(kthSmallest_stack, inp, out, times=10000)
